/*
 * [160] 链表中环的入口结点/相交链表
 *
 * 输入两个链表，找出它们的第一个公共结点
 *
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 例子：
/**

A:          a1 → a2
                    ↘
                     c1 → c2 → c3
                    ↗            
B:     b1 → b2 → b3


**/

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

// Definition for singly-linked list.
struct ListNode
{
  int val;
  struct ListNode* pnext;
  ListNode(int x) : val(x), pnext(NULL) {}
};

class Solution
{
 public:
  // leetcode 160题 相交链表
  /*ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return NULL;

        ListNode* p = headA;
        ListNode* q = headB;
        int m,n=0;
        while(p)
        {
          p=p->next;
          m++;
        }
        while(q)
        {
          q=q->next;
          n++;
        }
        ListNode* first;
        ListNode* second;
        first=headA;
        second=headB;
        int bettween =m-n;
        while(bettween>0&&first->next)
        {
          first=first->next;
          bettween--;
        }
        while(bettween<0&&second->next)
        {
          second=second->next;
          bettween++;
        }

        // 同时出发
        while(first!=second && first && second)
        {

          first=first->next;
          second=second->next;
        }

        return first;

    }*/

  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
  {
    auto p = headA, q = headB;
    while (p != q)
    {
      if (p)
        p = p->next;
      else
        p = headB;  // 妙，接着遍历
      if (q)
        q = q->next;
      else
        q = headA;
    }

    return p;
  }

  ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
  {
    // 求两链表的长度
    int len1 = findListLength(pHead1);
    int len2 = findListLength(pHead2);

    ListNode *plong = pHead1, *pshort = pHead2;
    if (len1 < len2)
    {
      pshort = pHead1;
      plong = pHead2;
    }
    // 较长的链表多走几步
    for (int i = 1; i <= abs(len1 - len2); i++) plong = plong->pnext;

    // 同时步进，直到遇到相同结点或者均遇到尾结点
    while (plong != pshort)
    {
      plong = plong->pnext;
      pshort = pshort->pnext
    }
    return plong;
  }

 private:
  int findListLength(ListNode* p)
  {
    int n = 0;
    while (p != nullptr)
    {
      p = p->pnext;
      n++;
    }
    return n;
  }
};

int main()
{
  class Solution solute;
  ListNode* prehead = new ListNode(-1);

  ListNode* head = new ListNode(1);
  prehead->pnext = head;

  ListNode* node2 = new ListNode(2);
  head->pnext = node2;
  node2->pnext = nullptr;

  ListNode* node3 = new ListNode(2);
  node2->pnext = node3;
  node3->pnext = nullptr;

  ListNode* node4 = new ListNode(3);
  node3->pnext = node4;
  node4->pnext = nullptr;

  ListNode* node5 = new ListNode(5);
  node4->pnext = node5;
  node5->pnext = node2;

  ListNode* entry = solute.detectCycle(head);

  return 0;
}

// @lc code=end
